Hierarchical scheduling is a technique for allocating CPU time among groups of processes (or equivalently, tasks or threads) in a multitasking environment. A hierarchical scheduler allows a scheduler (represented by the root of a scheduling tree) to allocate CPU time to a hierarchy of run queues, with each run queue containing a group of runnable processes. For example, the scheduler allocates the CPU time of a CPU to groups or processes, which are one-level below the root in the hierarchy. Each of these groups and processes partitions the CPU time that it is allocated with among its subgroups or sub-processes. Allocation of the CPU time continues among the children and descendants of the subgroups/sub-processes until a leaf of the scheduling tree is reached.
A hierarchical scheduler can be used to enforce fairness among processes and groups. For example, suppose that Alice has 10 processes to run and Ben has 40 processes to run. A hierarchical scheduler can treat Alice's 10 processes as one group and Ben's 40 processes as another group, and allocate 50% of CPU time to each of Alice's group and Ben's group. The hierarchical scheduler can enforce fairness between Alice's group and Ben's group. Once the scheduler decides who deserves the CPU time, it will perform fair scheduling among that user's processes. In addition to per-user-based groups, processes can also be organized based on user's roles, process types, or any categories that a system administrator sees fit.
In a multitasking environment, it is often useful for a program or process to temporarily yield the CPU time to another process; e.g., when the other process is holding a resource that the current process needs to make progress. With a classical round-robin scheduler, the yielding process is placed at the back of the run queue. As a result, the yielding process will lose its fair share of CPU time as it has to wait for all of the other processes in the run queue. A hierarchical scheduler does not maintain all of its processes in a linear run queue. Rather, a conventional hierarchical scheduler may assign the yielding process a very low priority, which would be the same (or similar) priority assigned to a process that has consumed a lot of CPU time. However, if the group that contains the yielding process keeps its current high priority, the group, as well as the yielding process, may get selected again. Thus, assigning the yielding process a very low priority may not achieve anything, unless the priority of its group (that contains the yielding process) is also adjusted. Conversely, adjusting the group priority would penalize all of the processes in the group, not just the yielding process. Therefore, there is a need for a hierarchical scheduler to properly manage a yielding process while maintaining scheduling fairness.